OI

OI Structures

1 基本数据结构

  • 1. 数组
  • 2. 链表, 双向链表
  • 3. 队列, 单调队列, 双端队列
  • 4. 栈, 单调栈

2 中级数据结构

  • 1. 堆
  • 2. 并查集与带权并查集
  • 3. hash 表
  • - 自然溢出
  • - 双hash

3 高级数据结构

  • 1. 树状数组
  • 2. 线段树, 线段树合并
  • 3. 平衡树
  • - Treap 随机平衡二叉树
  • - Splay 伸展树
  • - * Scapegoat Tree 替罪羊树
  • 4. 块状数组, 块状链表
  • 5.* 树套树
  • - 线段树套线段树
  • - 线段树套平衡树
  • - * 平衡树套线段树
  • 6.可并堆
  • - 左偏树
  • - *配对堆
  • 7. KDtree, 四分树

4 可持久化数据结构

  • 1. 可持久化线段树
  • - 主席树
  • 2. * 可持久化平衡树
  • 3. * 可持久化块状数组

5 字符串相关算法及数据结构

  • 1. KMP
  • 2. AC 自动机
  • 3. 后缀数组
  • 4. *后缀树
  • 5. *后缀自动机
  • 6. 字典树 Trie
  • 7. manacher

6 图论相关

  • 1. 最小生成树
  • - Prim
  • - Kruskal
  • 2. 最短路, 次短路, 第K短路
  • - SPFA
  • - Dijkstra
  • - Floyd
  • 3. 图的连通
  • - 连通分量 (Tarjan)
  • - 割点, 割边
  • 4. 网络流
  • - 最大流
  • - 最小割
  • - 费用流
  • - 分数规划
  • 5. 树相关
  • - 树上倍增, 公共祖先
  • - 树链剖分
  • - 树的分治算法(点分治, 边分治, *动态树分治)
  • - 动态树 (LCT, *树分块)
  • - 虚树
  • - *prufer编码
  • 7. 拓扑排序
  • 8. 欧拉图
  • 9. 二分图
  • - *KM算法
  • - 匈牙利算法

7 数学相关

  • 1. (扩展)欧几里得算法, 筛法, 快速幂
  • - 斐蜀定理
  • - 更相减损术
  • 2. 欧拉函数与*降幂大法
  • 3. 费马小定理
  • 4. 排列组合
  • - lucas定理
  • 5. 乘法逆元
  • 6. 矩阵乘法
  • 7. 数学期望与概率
  • 8. 博弈论
  • - sg函数
  • - 树上删边游戏
  • 9. *拉格朗日乘子法
  • 10. 中国剩余定理
  • 11. 线性规划与网络流
  • 12. 单纯型线性规划
  • 13. 辛普森积分
  • 14. 模线性方程组
  • 15. 容斥原理与莫比乌斯反演
  • 16. 置换群
  • 17. 快速傅里叶变换
  • 18. *大步小步法(BSGS), 扩展BSGS

8 动态规划

  • 1. 一般, 背包, 状压, 区间, 环形, 树形, 数位动态规划
  • - 记忆化搜索
  • - 斯坦纳树
  • - 背包九讲
  • 2. 斜率优化与* 四边形不等式优化
  • 3. 环 - 外向树上的动态规划
  • 4. *插头动态规划

9 计算几何

  • 1. 计算几何基础
  • 2. 三维计算几何初步
  • 3. *梯形剖分与三角形剖分
  • 4. 旋转卡壳
  • 5. 半平面交
  • 6. pick定理
  • 7. 扫描线

10 搜索相关

  • 1. BFS, DFS
  • 2. A* 算法
  • 3. 迭代加深搜索, 双向广搜

11 特殊算法

  • 1. 莫队算法, *树上莫队
  • 2. 模拟退火
  • 3. 爬山算法
  • 4. 随机增量法

12 其它重要工具与方法

  • 1.模拟与贪心
  • 2. 二分, 三分法(求偏导)
  • 3. 分治, CDQ分治
  • 4. 高精度
  • 5. 离线
  • 6. ST表

13 STL

  • 1. map
  • 2. priority_queue
  • 3. set
  • 4. bitset
  • 5. rope

14 非常见算法

  • 1. *朱刘算法
  • 2. *弦图与区间图